package com.ryujung.dfs_backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution39 {
    /**
     * 思路：
     * 每个数字都可以使用多次，
     * dfs时，需要将同一个数相加多次，和>7则结束
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();

        Deque<Integer> stk = new ArrayDeque<>();
        dfs(candidates, target, 0, 0, stk, res);
        return res;
    }

    private void dfs(int[] candidates, int target, int curIndex,
                     int sum, Deque<Integer> stk, List<List<Integer>> res) {
        if (sum >= target) {
            if (sum == target) {
                res.add(new ArrayList<>(stk));
            }
            return;
        }

        for (int i = curIndex; i < candidates.length; i++) {
            // 如果当前值相加后sum<target,可以重复累加该值
            sum += candidates[i];
            stk.addLast(candidates[i]);
            // 每次选择一种dfs方式，重复当前或者继续向后遍历
            if (sum < target) {
                // 重复累加当前index的值，后再遍历当前index
                dfs(candidates, target, i, sum, stk, res);
            } else {
                // 需要继续向后遍历，index+1
                dfs(candidates, target, i + 1, sum, stk, res);
            }
            stk.removeLast();
            sum -= candidates[i];
        }
    }

    public static void main(String[] args) {
        Solution39 s = new Solution39();
        System.out.println(s.combinationSum(new int[]{2, 3, 5, 6, 7}, 7));
        System.out.println(s.combinationSum(new int[]{2, 3, 5}, 8));
    }
}